<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html><html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:pls="http://www.w3.org/2005/01/pronunciation-lexicon" xmlns:ssml="http://www.w3.org/2001/10/synthesis" xmlns:svg="http://www.w3.org/2000/svg">
  <head>
    <title>Lists</title>
    <link rel="stylesheet" type="text/css" href="docbook-epub.css"/>
    <link rel="stylesheet" type="text/css" href="kawa.css"/>
    <script src="kawa-ebook.js" type="text/javascript"/>
    <meta name="generator" content="DocBook XSL-NS Stylesheets V1.79.1"/>
    <link rel="prev" href="Sequences.xhtml" title="Sequences"/>
    <link rel="next" href="Vectors.xhtml" title="Vectors"/>
  </head>
  <body>
    <header/>
    <section class="sect1" title="Lists" epub:type="subchapter" id="Lists">
      <div class="titlepage">
        <div>
          <div>
            <h2 class="title" style="clear: both">Lists</h2>
          </div>
        </div>
      </div>
      <p>A pair (sometimes called a <em class="firstterm">dotted pair</em>) is a record structure
with two fields called the car and cdr fields (for historical
reasons). Pairs are created by the procedure <code class="literal">cons</code>. The
car and cdr fields are accessed by the procedures <code class="literal">car</code> and
<code class="literal">cdr</code>. The car and cdr fields are assigned by the procedures
<code class="literal">set-car!</code> and <code class="literal">set-cdr!</code>.
</p>
      <p>Pairs are used primarily to represent lists. A <em class="firstterm">list</em> can be
defined recursively as either the empty list or a pair whose
cdr is a list. More precisely, the set of lists is defined as
the smallest set <em class="replaceable"><code>X</code></em> such that:
</p>
      <div class="itemizedlist" epub:type="list">
        <ul class="itemizedlist" style="list-style-type: disc; ">
          <li class="listitem" epub:type="list-item">
            <p>The empty list is in <em class="replaceable"><code>X</code></em>.
</p>
          </li>
          <li class="listitem" epub:type="list-item">
            <p>If <em class="replaceable"><code>list</code></em> is in <em class="replaceable"><code>X</code></em>, then any pair whose cdr field contains
<em class="replaceable"><code>list</code></em> is also in <em class="replaceable"><code>X</code></em>.
</p>
          </li>
        </ul>
      </div>
      <p>The objects in the car fields of successive pairs of a list are
the elements of the list. For example, a two-element list
is a pair whose car is the first element and whose cdr is a
pair whose car is the second element and whose cdr is the
empty list. The length of a list is the number of elements,
which is the same as the number of pairs.
</p>
      <p>The empty list is a special object of its own type. It is not
a pair, it has no elements, and its length is zero.
</p>
      <p><span class="emphasis"><em>Note:</em></span> The above definitions imply that all lists have finite
length and are terminated by the empty list.
</p>
      <p>The most general notation (external representation) for
Scheme pairs is the “dotted” notation <code class="literal">(<em class="replaceable"><code>c1</code></em> . <em class="replaceable"><code>c2</code></em> )</code>
where <em class="replaceable"><code>c1</code></em> is the value of the car field and
<em class="replaceable"><code>c2</code></em> is the value of the cdr field.
For example <code class="literal">(4 . 5)</code> is a pair whose car is 4 and
whose cdr is 5. Note that <code class="literal">(4 . 5)</code> is the external representation
of a pair, not an expression that evaluates to a pair.
</p>
      <p>A more streamlined notation can be used for lists: the
elements of the list are simply enclosed in parentheses and
separated by spaces. The empty list is written <code class="literal">()</code>.
For example,
</p>
      <pre class="screen">(a b c d e)
</pre>
      <p>and
</p>
      <pre class="screen">(a . (b . (c . (d . (e . ())))))
</pre>
      <p>are equivalent notations for a list of symbols.
</p>
      <p>A chain of pairs not ending in the empty list is called an
<em class="firstterm">improper list</em>. Note that an improper list is not a list.
The list and dotted notations can be combined to represent
improper lists:
</p>
      <pre class="screen">(a b c . d)
</pre>
      <p>is equivalent to
</p>
      <pre class="screen">(a . (b . (c . d)))
</pre>
      <p><span class="emphasis"><em>Needs to finish merging from R7RS!</em></span>
</p>
      <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667874498048" class="indexterm"/> <code class="function">make-list</code> <em class="replaceable"><code>k</code></em> [<em class="replaceable"><code>fill</code></em>]</p>
      <div class="blockquote">
        <blockquote class="blockquote">
          <p>Returns a newly allocated list of <em class="replaceable"><code>k</code></em> elements.  If a second argument
is given, the each element is initialized to <em class="replaceable"><code>fill</code></em>.
Otherwise the initial contents of each element is unspecified.
</p>
          <pre class="screen">(make-list 2 3)   ⇒ (3 3)
</pre>
        </blockquote>
      </div>
      <span id="SRFI-1"/>
      <section class="sect2" title="SRFI-1 list library" epub:type="division" id="idm139667874492576">
        <div class="titlepage">
          <div>
            <div>
              <h3 class="title">SRFI-1 list library</h3>
            </div>
          </div>
        </div>
        <p>The <a class="ulink" href="http://srfi.schemers.org/srfi-1/srfi-1.html" target="_top">SRFI-1 List Library</a>
is available, though not enabled by default.  To use its functions you
must <code class="literal">(require 'list-lib)</code> or <code class="literal">(require 'srfi-1)</code>.
</p>
        <pre class="screen">(require 'list-lib)
(iota 5 0 -0.5) ⇒ (0.0 -0.5 -1.0 -1.5 -2.0)
</pre>
        <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667874489056" class="indexterm"/> <code class="function">reverse!</code> <em class="replaceable"><code>list</code></em></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>The result is a list consisting of the elements of <em class="replaceable"><code>list</code></em> in reverse order.
No new pairs are allocated, instead the pairs of <em class="replaceable"><code>list</code></em> are re-used,
with <code class="literal">cdr</code> cells of <em class="replaceable"><code>list</code></em> reversed in place.  Note that if <em class="replaceable"><code>list</code></em>
was pair, it becomes the last pair of the reversed result.
</p>
          </blockquote>
        </div>
        <span id="SRFI-101"/>
      </section>
      <section class="sect2" title="SRFI-101 Purely Functional Random-Access Pairs and Lists" epub:type="division" id="idm139667874482928">
        <div class="titlepage">
          <div>
            <div>
              <h3 class="title">SRFI-101 Purely Functional Random-Access Pairs and Lists</h3>
            </div>
          </div>
        </div>
        <p><a class="ulink" href="http://srfi.schemers.org/srfi-101/srfi-101.html" target="_top">SRFI-101</a>
specifies immutable (read-only) lists with fast (logarithmic) indexing
and functional
update (i.e. return a modified list).
These are implemented by a <code class="literal">RAPair</code> class
which extends the generic <code class="literal">pair</code> type, which means that most
code that expects a standard list will work on these lists as well.
</p>
      </section>
    </section>
    <footer>
      <div class="navfooter">
        <ul>
          <li>
            <b class="toc">
              <a href="Lists.xhtml#idm139667874492576">SRFI-1 list library</a>
            </b>
          </li>
          <li>
            <b class="toc">
              <a href="Lists.xhtml#idm139667874482928">SRFI-101 Purely Functional Random-Access Pairs and Lists</a>
            </b>
          </li>
        </ul>
        <p>
          Up: <a accesskey="u" href="Data-structures.xhtml">Data structures</a></p>
        <p>
        Previous: <a accesskey="p" href="Sequences.xhtml">Sequences</a></p>
        <p>
        Next: <a accesskey="n" href="Vectors.xhtml">Vectors</a></p>
      </div>
    </footer>
  </body>
</html>
